#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "psm.h"
#include "rINDUCTION.h"


/*

	The main difference with rINDUCTION2 is that now the startpoint is not ANY, but all the possible antiunifications of the 
	positive examples.

 */



bool rINDUCTIONHypothesis::learn3(List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model)
{
	FeatureTerm *solution;
	List<FeatureTerm> solutions;
	List< List<FeatureTerm> > descriptions;
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;

	/* Compute the different solutions: */ 
	{
		int pos;
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
/*
			{
				char *s=c->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/			
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;
			
			if (s!=0) {
				pos=solutions.Position(s);
				if (pos==-1) {
					solutions.Add(s);
					tmp=new List<FeatureTerm>;
					tmp->Add(d);
					descriptions.Add(tmp);
				} else {
					delete s;
					descriptions[pos]->Add(d);
				} /* if */ 
			} // if
		} /* while */ 
	}

	/* Compute the default solution: */ 
	{
		int max=-1;
		FeatureTerm *s;
		List<FeatureTerm> *tmp;

		m_default_solution=0;

		solutions.Rewind();
		descriptions.Rewind();

		while(solutions.Iterate(s) &&  descriptions.Iterate(tmp)) {
			if (max==-1 || tmp->Length()>max) {
				max=tmp->Length();
				delete m_default_solution;
				m_default_solution=new FeatureTerm(s);
			} /* if */ 
		} /* while */ 
	}

	solutions.Rewind();
	while(solutions.Iterate(solution)) {
		learn3_single_class(solution,cases,description_path,solution_path,o,domain_model);
	} /* while */ 

	return true;
} /* rINDUCTIONHypothesis::learn3 */ 




bool rINDUCTIONHypothesis::learn3_single_class(FeatureTerm *solution,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model)
{
	int step=0;
	List<FeatureTerm> positive;
	List<FeatureTerm> negative;

	/* Learn a set of patterns for the current solution: */ 
	{
		char *s=solution->toStringNOOS(domain_model);
		printf("\nrINDUCTION3: building model for %s --------------------------------------------------\n\n",s);
		delete []s;
	}

	/* Create the positive and negative examples lists: */ 
	{
		FeatureTerm *c,*s,*d;
		List<FeatureTerm> l,*tmp;

		l.Instance(*cases);
		while(l.Iterate(c)) {
			tmp=c->readPath(description_path);
			if (tmp->Length()==1) d=tmp->ExtractIni();
							 else d=0;
			delete tmp;
			tmp=c->readPath(solution_path);
			if (tmp->Length()==1) s=tmp->ExtractIni();
							 else s=0;
			delete tmp;

			if (s!=0) {
				if (solution->equivalents(s)) {
					positive.Add(d);
				} else {
					negative.Add(d);
				} /* if */ 
				delete s;
			} // if
		} /* while */ 
	}

	if (negative.EmptyP()) {
		FeatureTerm *pattern=new FeatureTerm((Symbol *)0,o->get_sort("any"),0);

		printf("rINDUCTION3: rule found, covers %i positive examples\n",positive.Length());
		{
			char *s1,*s2;
			s1=solution->toStringNOOS(domain_model);
			s2=pattern->toStringNOOS(domain_model);
			printf("rINDUCTION3: rule is for class %s,\n%s\n\n",s1,s2);
			delete []s1;
			delete []s2;
		}
		fflush(0);

		m_patterns.Add(pattern);
		m_solutions.Add(new FeatureTerm(solution));
		m_reliability.Add(new float(1));
		positive.Delete();
		negative.Delete();
	} else {

		/* find the shortest description that covers only positive examples: */ 
		FeatureTerm *description,*d,*refinement,*problem;
		List<FeatureTerm> open_descriptions;
		List<int> open_coverage;
		List<bool> open_positive_coverage;
		List<FeatureTerm> *refinements;
		bool valid,is_solution,*positive_coverage;
		int i;

		printf("rINDUCTION3: %i positive, %i negative\n",positive.Length(),negative.Length());
		fflush(0);

		/* Antiunification of all the positive examples: */ 
		{
//			antiunification(&open_descriptions,&positive,SPECIALIZATION_LANGUAGE_L0,0,o,domain_model,true,AU_VERSION_STANDARD);
			antiunification(&open_descriptions,&positive,SPECIALIZATION_LANGUAGE_L2,0,o,domain_model,true,AU_VERSION_STANDARD);
			{
				printf("Antiunification computed: %i terms\n",open_descriptions.Length());
				open_descriptions.Rewind();
				while (open_descriptions.Iterate(d)) {
					{
						char *s;
						s=d->toStringNOOS(domain_model);
						printf("%s\n",s);
						fflush(0);
						delete []s;
					}

					open_coverage.Add(new int(positive.Length()));
					positive_coverage=new bool[positive.Length()];
					for(i=0;i<positive.Length();i++) positive_coverage[i]=true;
					open_positive_coverage.Add(positive_coverage);
				} /* while */ 
			}
		} 

		/* Determine whether any antiunification does not subsume any negative example: */ 
		{
			bool is_solution;
			bool definitive=false;

			open_descriptions.Rewind();
			open_positive_coverage.Rewind();
			while(!definitive && open_descriptions.Iterate(description) && open_positive_coverage.Iterate(positive_coverage)) {
				is_solution=true;
				negative.Rewind();
				while(negative.Iterate(problem) && is_solution) {
					if (description->subsumes(problem)) is_solution=false;
				} /* while */ 

				if (is_solution) {
					description=generalize_pattern_systematic(description,&positive,&negative,o,domain_model);

					m_patterns.Add(description);
					m_solutions.Add(new FeatureTerm(solution));
					m_reliability.Add(new float(1));
					{
						bool *pc;
						pc=new bool[positive.Length()];
						for(i=0;i<positive.Length();i++) {
							if (description->subsumes(positive[i])) pc[i]=true;
															   else pc[i]=false;
						} /* for */ 
						m_positive_coverage.Add(pc);
					}

					printf("rINDUCTION3: new rule found , covers %i positive examples and %i negative examples\n",positive.Length(),0);
					show_coverage(positive_coverage,positive.Length());
					fflush(0);
					{
						char *s1,*s2;
						s1=solution->toStringNOOS(domain_model);
						s2=description->toStringNOOS(domain_model);
						printf("rINDUCTION3: rule is for class %s,\n%s\n\n",s1,s2);
						fflush(0);
						delete []s1;
						delete []s2;
					}					

					/* A definitive pattern has been found. No need for more patterns!! */ 
					definitive=true;
				} /* if */ 
			}

			if (definitive) {
				open_descriptions.Delete();
				open_coverage.Delete();
				open_positive_coverage.Delete();
			} /* if */ 
		} 


		while(!open_descriptions.EmptyP()) {
			bool new_pattern=false;

			step++;

			printf("%i - %i\n",step,open_descriptions.Length());
			fflush(0);

/*
			if ((step%500)==0) 
			{

				char *s;
				FeatureTerm *f;
				open_descriptions.Rewind();
				while(open_descriptions.Iterate(f)) {
					s=f->toStringNOOS(domain_model);
					printf("%s\n",s);
					delete []s;
				} // while  
			} // if  
*/
//				SELECTION METHOD 2: most general by subsumption
			{
				FeatureTerm *f=0;
				int *max_c=0,*c;
				bool *pc=0,*max_pc=0;

				description=0;
				open_descriptions.Rewind();
				open_coverage.Rewind();
				open_positive_coverage.Rewind();
				while(open_descriptions.Iterate(f) && open_coverage.Iterate(c) && open_positive_coverage.Iterate(pc)) {
					if (description==0 || f->subsumes(description)) {
						description=f;
						max_c=c;
						max_pc=pc;
					} // if  
				} // while  

//					printf("%i\n",*max_c);

				open_descriptions.DeleteElement(description);
				open_coverage.DeleteElement(max_c);
				open_positive_coverage.DeleteElement(max_pc);
				delete max_c;
				positive_coverage=max_pc;
			}

//			refinements = DSpecializationL0_b(description,&positive,domain_model);
			refinements = DSpecializationL2_b(description,&positive,0,o,domain_model);

			while(!refinements->EmptyP()) {
				int positive_covered=0;
//					int negative_covered=0;

				refinement=refinements->ExtractIni();

				valid=false;
				i=0;
				positive.Rewind();
				while(positive.Iterate(problem) && !valid) {
					if (positive_coverage[i] && refinement->subsumes(problem)) valid=true;
					i++;
				} /* while */ 
/*
				if (refinement->subsumes(description)) {
					{
						char *s;
						printf("SPECIALIZATION ERROR!!!!\n");
						printf("Original:\n");
						s=description->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
						printf("Specialization:\n");
						s=refinement->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
					}
					valid=false;
				} // if  
*/
				if (valid) {
/*
					{
						char *s;
						s=refinement->toStringNOOS(domain_model);
						printf("Refinement:\n%s\n\n",s);
						delete []s;
					}
*/
					is_solution=true;
					negative.Rewind();
					while(negative.Iterate(problem) && is_solution) {
						if (refinement->subsumes(problem)) is_solution=false;
					} /* while */ 

					if (is_solution) {
						/* Solution found!!!: */ 
						bool *coverage=new bool[positive.Length()];

						i=0;
						positive.Rewind();
						while(positive.Iterate(problem)) {
							if (positive_coverage[i] && refinement->subsumes(problem)) {
								positive_covered++;
								coverage[i]=true;
							} else {
/*
								if (refinement->subsumes(problem)) {
									printf("ERROR 1!!!!\n");
									if (description->subsumes(problem)) printf("Even description also subsumes the example!!\n");
									{
										char *s;
										s=description->toStringNOOS(domain_model);
										printf("Description:\n%s\n",s);
										delete []s;
										s=refinement->toStringNOOS(domain_model);
										printf("Refinement:\n%s\n",s);
										delete []s;
										printf("The problem occurred in positive example %i\n",i);
									}
								} // if  
*/
								coverage[i]=false;
							} /* if */ 
							i++;
						} /* while */ 

						if (new_coverage_p(solution,coverage,positive.Length())) {
							int i;
							FeatureTerm *gr,*f;
							List<FeatureTerm> pos,neg;

							i=0;
							positive.Rewind();
							while(positive.Iterate(f)) {
								if (coverage[i]) pos.Add(f);
//												else neg.Add(f);
								i++;
							} /* while */ 
							negative.Rewind();
							while(negative.Iterate(f)) neg.Add(f);

							gr=generalize_pattern_systematic(refinement,&pos,&neg,o,domain_model);
							while(!pos.EmptyP()) pos.ExtractIni();
							while(!neg.EmptyP()) neg.ExtractIni();

							delete refinement;
							refinement=gr;

							new_pattern=true;
							m_patterns.Add(refinement);
							m_solutions.Add(new FeatureTerm(solution));
							m_reliability.Add(new float(1));
							{
								bool *pc;
								pc=new bool[positive.Length()];
								for(i=0;i<positive.Length();i++) {
									if (refinement->subsumes(positive[i])) pc[i]=true;
																	  else pc[i]=false;
								} /* for */ 
								m_positive_coverage.Add(pc);
								delete []coverage;
								coverage=pc;
							}

							printf("rINDUCTION3: new rule found , covers %i positive examples and %i negative examples\n",positive_covered,0);
							show_coverage(coverage,positive.Length());
							fflush(0);
							{
								char *s1,*s2;
								s1=solution->toStringNOOS(domain_model);
								s2=refinement->toStringNOOS(domain_model);
								printf("rINDUCTION3: rule is for class %s,\n%s\n\n",s1,s2);
								fflush(0);
								delete []s1;
								delete []s2;
							}					
							fflush(0);

							if (positive_covered==positive.Length()) {
								/* A definitive pattern has been found. No need for more patterns!! */ 
								open_descriptions.Delete();
								open_coverage.Delete();
								open_positive_coverage.Delete();
								refinements->Delete();
							} /* if */ 
						} else {
//								printf("rINDUCTION3: new rule found, but does not have new coverage: ");
//								show_coverage(coverage,positive.Length());
							delete refinement;
							delete []coverage;
							
						} /* if */ 
					} else {
						bool advances=true;

						open_descriptions.Rewind();
						while(open_descriptions.Iterate(d) && advances) {
							if (refinement->subsumes(d)) advances=false;
						} /* while */ 

						if (advances) {
							int count=0;
							bool *coverage=new bool[positive.Length()];

							i=0;
							positive.Rewind();
							while(positive.Iterate(problem)) {
								if (positive_coverage[i] && refinement->subsumes(problem)) {
									count++;
									coverage[i]=true;
								} else {
/*
									if (refinement->subsumes(problem)) {
										printf("ERROR 2!!!!\n");
									} // if  
*/
									coverage[i]=false;
								} /* if */ 
								i++;
							} /* while */ 

							if (new_coverage_p(solution,coverage,positive.Length())) {
								/* Delete all the descriptions more general than "refinement": */ 
/*
								{
									List<FeatureTerm> to_delete;
									List<int> to_delete_i;
									List<bool> to_delete_b;
									int *c;
									bool *pc;

									open_descriptions.Rewind();
									open_coverage.Rewind();
									open_positive_coverage.Rewind();
									while(open_descriptions.Iterate(d) && open_coverage.Iterate(c) && open_positive_coverage.Iterate(pc)) {
										if (d->subsumes(refinement)) {
											bool del=true;
											
											for(i=0;i<positive.Length();i++) {
												if (pc[i] && !coverage[i]) del=false;
											} // for  

											if (del) {
												to_delete.Add(d);
												to_delete_i.Add(c);
												to_delete_b.Add(pc);
											} // if  
										} // if 
									} // while  

//										printf("%i/%i eliminated\n",to_delete.Length(),open_descriptions.Length());

									while(!to_delete.EmptyP()) {
										d=to_delete.ExtractIni();
										open_descriptions.DeleteElement(d);
										delete d;
									} // while 
									while(!to_delete_i.EmptyP()) {
										c=to_delete_i.ExtractIni();
										open_coverage.DeleteElement(c);
										delete c;
									} // while  
									while(!to_delete_b.EmptyP()) {
										pc=to_delete_b.ExtractIni();
										open_positive_coverage.DeleteElement(pc);
										delete pc;
									} // while  
								}
*/

//									printf("Add this refinement\n");
								open_descriptions.Add(refinement);
								open_coverage.Add(new int(count));
								open_positive_coverage.Add(coverage);
							} else {
								delete refinement;
								delete []coverage;
							} /* if */ 
						} else {
							delete refinement;
						} /* if */ 
					} /* if */ 
				} else {
					delete refinement;
				} /* if */ 

			} /* while */ 
			delete []positive_coverage;
			delete refinements;
			delete description;
			
			/* Filter current open descriptions: */ 
			if (new_pattern) {
				List<FeatureTerm> to_delete;
				List<int> to_delete_i;
				List<bool> to_delete_b;
				int *c;
				bool *pc;

				open_descriptions.Rewind();
				open_coverage.Rewind();
				open_positive_coverage.Rewind();
				while(open_descriptions.Iterate(d) && open_coverage.Iterate(c) && open_positive_coverage.Iterate(pc)) {
//						show_coverage(coverage,positive.Length());
					if (!new_coverage_p(solution,pc,positive.Length())) {
						to_delete.Add(d);
						to_delete_i.Add(c);
						to_delete_b.Add(pc);
					} /* if */ 
				} /* while */ 

				printf("%i/%i eliminated\n",to_delete.Length(),open_descriptions.Length());
				fflush(0);

				while(!to_delete.EmptyP()) {
					d=to_delete.ExtractIni();
					open_descriptions.DeleteElement(d);
					delete d;
				} /* while */ 
				while(!to_delete_i.EmptyP()) {
					c=to_delete_i.ExtractIni();
					open_coverage.DeleteElement(c);
					delete c;
				} /* while */ 
				while(!to_delete_b.EmptyP()) {
					pc=to_delete_b.ExtractIni();
					open_positive_coverage.DeleteElement(pc);
					delete pc;
				} /* while */ 

				new_pattern=false;
			} /* if */ 


		} /* while */ 
	} /* if */ 

	filter_rules(solution,positive.Length(),o,domain_model);

	return true;
} /* rINDUCTIONHypothesis::learn3_single_class */ 




FeatureTerm *rINDUCTIONHypothesis::generalize_pattern_systematic(FeatureTerm *pattern,List<FeatureTerm> *positive,List<FeatureTerm> *negative,Ontology *o,FTKBase *domain_model)
{
	List<FeatureTerm> nodes,open_nodes;
	List<FeatureTerm> to_delete,to_delete_open;
	List<FeatureTerm> l3;
	List<FeatureTerm> *l;
	FeatureTerm *f,*f2,*d;
	bool c1,c2;

/*
	FeatureTerm *control;
	bool control_reachable;
	bool perform_control=false;
	control=domain_model->fromStringNOOS("(define (trains-description) "
										 "  (cars (define (car)	"
										 "         (cshape jaggedtop)))) ",o);
	if (control->subsumes(pattern)) perform_control=true;
*/

	{
		char *s;
		printf("Generalizing:\n");
		s=pattern->toStringNOOS(domain_model);
		printf("%s\n",s);
		fflush(0);
	}

	f=new FeatureTerm(pattern);
	open_nodes.Add(f);

	while(!open_nodes.EmptyP()) {
		f=open_nodes.ExtractIni();
		l=DGeneralization(f,o,domain_model);
		{
			bool advances=true;
			nodes.Rewind();
			while(advances && nodes.Iterate(f2)) {
				if (f2->subsumes(f)) {
					advances=false;
				} /* if */ 
			} /* while */ 

			if (advances) {
				nodes.Add(f);
			} else {
				delete f;
			} /* if */ 
		}
//		printf("*- %i - %i ---- Now %i generated --------*\n",nodes.Length(),open_nodes.Length(),l->Length());
//		fflush(0);
/*
		{
			char *s;
			s=f->toStringNOOS(domain_model);
			printf("Base: \n%s\n",s);
			delete []s;
		}
*/
		l->Rewind();
		while(l->Iterate(f2)) {
/*
			{
				char *s;
				s=f2->toStringNOOS(domain_model);
				printf("Considering: \n%s\n",s);
				delete []s;
			}
*/			
			c1=true;
			l3.Instance(*positive);
			l3.Rewind();
			while(l3.Iterate(d) && c1) {
				if (!f2->subsumes(d)) {
					c1=false;
/*
					{
						char *s;
						s=d->toStringNOOS(domain_model);
						printf("Does not subsume: \n%s\n",s);
						delete []s;
					}
*/
				} /* if */ 
			} /* while */ 

			c2=true;
			l3.Instance(*negative);
			l3.Rewind();
			while(l3.Iterate(d) && c1 && c2) {
				if (f2->subsumes(d)) c2=false;
			} /* while */ 

			if (c1 && c2) {
				bool advances=true;

//				printf("Conistent\n");

				nodes.Rewind();
				while(advances && nodes.Iterate(f)) {
					if (f->subsumes(f2)) {
						advances=false;
					} /* if */ 
					if (f2->subsumes(f)) {
						to_delete.Add(f);
					} /* if */ 
				} /* while */ 
				
				open_nodes.Rewind();
				while(advances && open_nodes.Iterate(f)) {
					if (f->subsumes(f2)) {
						advances=false;
					} /* if */ 
//					if (f2->subsumes(f)) {
//						to_delete_open.Add(f);
//					} /* if */ 
				} /* while */  

				if (advances) {

//					printf("Advances\n");

					while(!to_delete.EmptyP()) {
						f=to_delete.ExtractIni();
						nodes.DeleteElement(f);
/*
						{
							char *s;
							s=f->toStringNOOS(domain_model);
							printf("Deleted [nodes]: \n%s\n",s);
							delete []s;
						}
*/
					  delete f;
					} /* while */ 
/*
					while(!to_delete_open.EmptyP()) {
						f=to_delete_open.ExtractIni();
						open_nodes.DeleteElement(f);
						{
							char *s;
							s=f->toStringNOOS(domain_model);
							printf("Deleted [open_nodes]: \n%s\n",s);
							delete []s;
						}
						delete f;
					} // while 
*/
					open_nodes.Insert(new FeatureTerm(f2));
//					open_nodes.Add(new FeatureTerm(f2));
				} else {
					while(!to_delete.EmptyP()) to_delete.ExtractIni();
//					while(!to_delete_open.EmptyP()) to_delete_open.ExtractIni();
				} /* if */ 

				// INTEGRITY TEST: 
/*
				if (perform_control) {
					bool control_reachable=false;

					nodes.Rewind();
					while(!control_reachable && nodes.Iterate(f)) {
						if (control->subsumes(f)) control_reachable=true;
					} // while 
					open_nodes.Rewind();
					while(!control_reachable && open_nodes.Iterate(f)) {
						if (control->subsumes(f)) control_reachable=true;
					} // while  

					if (!control_reachable) printf("CONTROL IS NOT REACHABLE!!!!!!!!!!!!!!!!!!\n\n");
				}
*/
			} /* if */ 
		} /* if */ 
		delete l;
	} /* while */ 

	{
		FeatureTerm *min_cost_f=0;
		int min_cost=0;
		char *s;

		printf("Result (%i terms):\n",nodes.Length());
		nodes.Rewind();
		while(nodes.Iterate(f)) {
			{
				List<FeatureTerm> tmp;
				List<int> tmp_l;
				Generalize(f,0,&tmp,&tmp_l,o,domain_model,true);
				printf("With cost: %i\n",*tmp_l[0]);
				if (min_cost_f==0 || *tmp_l[0]<min_cost) {
					min_cost_f=f;
					min_cost=*tmp_l[0];
				} /* if */ 
			}
			s=f->toStringNOOS(domain_model);
			printf("%s\n",s);
		} // while 
		fflush(0);

		f=new FeatureTerm(min_cost_f);
	}

	return f;
} /* rINDUCTIONHypothesis::generalize_pattern_systematic */ 
